
# def QuickSort(r):
# def SelectSort(r):
def  HeapSort(r):
    
    def headadjust(arr,start,end):
        temp=arr[start]
        son=start*2+1
        while son<=end:
            if son<end and arr[son]<arr[son+1]:  #找出左右孩子节点较大的
                son+=1
            if temp>=arr[son]:       #判断是否为大顶堆
                break
            arr[start]=arr[son]     #子节点上移
            start=son                     #继续向下比较
            son=2*son+1
        arr[start]=temp             #将原堆顶插入正确位置
    n=len(r)
    if n<=1:
        return r
        
    root=n//2-1
    while root>=0:
        headadjust(r,root,n-1)
        root-=1
        pass
    i=n-1
    while(i>=0):
        r[0],r[i]=r[i],r[0]
        headadjust(r,0,i-1)
        i-=1
    return r


        
    

r = [1, 5, 3, 2, 4]
# print(QuickSort(r))
# print(SelectSort(r))
print(HeapSort(r))
